The present invention relates generally to data processing systems and, more particularly, to recursively partitioning networks.
Networks comprise a number of nodes that are interconnected via links. As used herein, the term xe2x80x9cnodexe2x80x9d refers to any device capable of communicating, such as a computer, router, switch, network processor, or symmetric multi-processor. The specific configuration of nodes and links in a network is referred to as the xe2x80x9cnetwork topology.xe2x80x9d
Some conventional networks may be partitioned into subnetworks. The xe2x80x9cpartitioningxe2x80x9d of a network refers to subdividing the network into two subnetworks, each of which is independent of the other. The term xe2x80x9cindependentxe2x80x9d refers to each link of the original network belonging to at most one of the two resulting subnetworks and each node of the original network belonging to at most one of the two resulting subnetworks.
Partitioning a network is desirable because it provides fault tolerance. That is, partitioning a network into two subnetworks ensures that the failure of a node in one subnetwork does not affect the other. For example, a node in one of the subnetworks may fail and become nonoperational. In this situation, although the failure affects performance of the subnetwork in which it resides because none of the other nodes can route traffic through the failed node, the other subnetwork remains unaffected by the failure.
Although conventional systems exist for partitioning a network, these systems partition the network in a restricted manner: each subnetwork is constrained as to the number of nodes that it contains. For example, in one conventional system, each subnetwork contains either one-half or one-fourth of the total number of nodes in the network. Similarly, another conventional system restricts the number of nodes in the network to a power of 2.
Although these conventional systems allow for partitioning, because the number of nodes in the subnetwork is constrained, these systems are inflexible, which can lead to the under utilization of resources. For example, in the conventional system where each subnetwork contains either one-half or one-fourth of the total number of nodes, if the total number of nodes were 16 and the system administrator needed a subnetwork of only 3 nodes to run a particular set of programs, the administrator would be restricted to dividing the network into two subnetworks of 8 nodes or a subnetwork of 4 nodes and a subnetwork of 12 nodes. In either case, at least one node goes underutilized. It is therefore desirable to improve the partitioning of networks.
Methods and systems consistent with the present invention provide a family of networks ranging from 2 nodes to 16 nodes that can be partitioned in an unconstrained manner. That is, where the number of nodes in one of these networks is N, each subnetwork can contain any number of nodes from 1 to Nxe2x88x921 as long as the total number of nodes in both subnetworks equals N. Furthermore, each subnetwork can be partitioned repeatedly until reaching the atomic level (i.e., when the subnetwork contains a single node). In accordance with methods and systems consistent with the present invention, when a network is partitioned, each subnetwork has various desirable properties. For example, the maximum path length between any two nodes in each subnetwork is 3, and each subnetwork has a set of deadlock-free routings.
In accordance with methods consistent with the present invention, a method is provided in a data processing system with a number of nodes N, where N is greater than 4. This method receives an indication of a first number of nodes and a second number of nodes. The first number of nodes and the second number of nodes are capable of being any number from 1 to Nxe2x88x921 as long as the sum of the first number of nodes and the second number of nodes is N. Furthermore, the method partitions the nodes into a first subnetwork having the first number of nodes and a second subnetwork having the second number of nodes.
In accordance with methods consistent with the present invention, a method is provided that provides a network that has nodes and a plurality of the nodes are partner nodes having a partnership relationship. Furthermore, the method partitions the network into a plurality of subnetworks such that the partnership relationship between the partner nodes remains intact.
In accordance with methods consistent with the present invention, a method is provided in a distributed system having a network of nodes. This method partitions the network into a plurality of subnetworks, provides each of the subnetworks with a routing table that avoids deadlock, and routes traffic through each of the subnetworks using the provided routing tables such that deadlock is avoided.
In accordance with systems consistent with the present invention, an administrative node of a network is provided. The network contains a number of nodes N, where N is greater than 4. This administrative node contains a memory and a processor. The memory comprises routing software with first code that receives an indication of a first number of nodes and an indication of a second number of nodes, the first number and the second number being unconstrained such that the first number and the second number are capable of being any number between 1 and Nxe2x88x921 as long as the first number and the second number sum to N. The routing software also contains second code for partitioning the network into a first partition with the first number of nodes and a second partition with the second number of nodes. The processor runs the routing software.